This invention relates to a method for searching the graphic data included in a specified range of a graphic image displayed on a display screen in an application of map data, for example, and more particularly to a such a searching method as is preferably adapted to the case where high speed imprementation is required.
In order to effectively process graphic data on a multi-dimensional coordinate space, which are required, in an application of map data, for example, there is required such an index mechanism as can search the graphic data included in a specified range at a high speed.
As such a searching method of multi-dimensional data, several kinds of method have been investigated. For example, the method called the "cell technique" is proposed in Computing Surveys. Vol. 11, No. 4, Dec. 1979 pp. 400 to 401 (herein after referred to as reference 1). The cell technique is as follows. Point data, which means the data each having only a position but not having a size or width, is previously partitioned in a grid form in accordance with their spacial position. In searching the data, first, the cells with which the search range overlaps are checked. The data is read out only from the cells overlapped with the search range. The inclusive relation between the positions of the data and the search range is checked to provide a final search result. In this way, the number of data to be checked is limited compared with the method of checking all the data positions thus a high speed search can be realized.
Further, a method of searching multi-dimension data using the above-described cell technique is disclosed in Japanese Patent Unexamined Publication No. 58-117,077 (hereinafter referred to as reference 2). In this search method, by using the characteristic that if the two-dimensional coordinate space on which two-dimensional graphics are arranged is partitioned in plural cells, each graphic belongs to any cell region in its entirety or portion, the addresses of the graphic data, etc. within each cell region are previously registered collectively. In searching the data, only by searching the cells which satisfy a specified region condition, only the graphic data within the specified region can be searched.
In the references 1 and 2, there is only disclosed a method for searching graphic data but not disclosed a technique of adding or deleting the graphic data. However, in the application described above of such a system being used in map data there is required an index mechanism that can performed operations such as addition or deletion of data at high speed.